//package com.yizn.Algorithm;
//
//import javax.swing.tree.TreeNode;
//import java.util.*;
//
///**
// * Hello world!
// *
// */
//public class App
//{
//    public static void main( String[] args )
//    {
//        System.out.println( "Hello World!" );
//    }
//}
//
//
////反转链表
///**
// * Definition for singly-linked list.
// */
// class ListNode {
//      int val;
//      ListNode next;
//      ListNode(int x) { val = x; }
//  }
//
//class Solution {
//    public ListNode reverseList(ListNode head) {
//        if(head == null){
//            return null;
//        }
//        ListNode last = null;
//        while(head != null){
//            ListNode tmp = head;
//            head = head.next;
//            tmp.next = last;
//            last = tmp;
//        }
//        return last;
//
//    }
//}
////合并两个有序链表
///**
// * Definition for singly-linked list.
// * public class ListNode {
// *     int val;
// *     ListNode next;
// *     ListNode(int x) { val = x; }
// * }
// */
//class Solution {
//    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//        ListNode dummyHead = new ListNode(0);
//        ListNode cur = dummyHead;
//        while (l1 != null && l2 != null) {
//            if (l1.val < l2.val) {
//                cur.next = l1;
//                cur = cur.next;
//                l1 = l1.next;
//            } else {
//                cur.next = l2;
//                cur = cur.next;
//                l2 = l2.next;
//            }
//        }
//        // 任一为空，直接连接另一条链表
//        if (l1 == null) {
//            cur.next = l2;
//        } else {
//            cur.next = l1;
//        }
//        return dummyHead.next;
//
//    }
//}
//
////判断一个链表是否有环，并找出环的入口-- 环形链表 II
///**
// * Definition for singly-linked list.
// * class ListNode {
// *     int val;
// *     ListNode next;
// *     ListNode(int x) {
// *         val = x;
// *         next = null;
// *     }
// * }
// */
//public class Solution {
//    public ListNode detectCycle(ListNode head) {
//        ListNode fast = head;
//        ListNode slow = head;
//        while(fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//            if(fast == slow) {
//                break;
//            }
//        }
//        //没有环  返回null
//        if(fast == null || fast.next == null){
//            return null;
//        }
//        slow = head;
//        while(fast != slow) {
//            fast = fast.next;
//            slow = slow.next;
//        }
//        return slow;
//
//    }
//}
//
////4.二叉树的按层遍历（或者换成“二叉树之字形遍历”）-- 二叉树的层次遍历
///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode(int x) { val = x; }
// * }
// */
//class Solution {
//    public List<List<Integer>> levelOrder(TreeNode root) {
//        if(root == null)
//            return new ArrayList<>();
//        List<List<Integer>> res = new ArrayList<>();
//        Queue<TreeNode> queue = new LinkedList<TreeNode>();
//        queue.add(root);
//        while(!queue.isEmpty()){
//            int count = queue.size();
//            List<Integer> list = new ArrayList<Integer>();
//            while(count > 0){
//                TreeNode node = queue.poll();
//                list.add(node.val);
//                if(node.left != null)
//                    queue.add(node.left);
//                if(node.right != null)
//                    queue.add(node.right);
//                count--;
//            }
//            res.add(list);
//        }
//        return res;
//
//    }
//}
////5.	实现一个函数，检查二叉树是否平衡。--平衡二叉树
///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode(int x) { val = x; }
// * }
// */
//class Solution {
//    public boolean isBalanced(TreeNode root) {
//        if(root == null){
//            return true;
//        }
//        if(Math.abs(getDepth(root.left)-getDepth(root.right))<=1){
//            return isBalanced(root.left)&&isBalanced(root.right);
//        }else{
//            return false;
//        }
//
//
//
//    }
//
//    public int getDepth(TreeNode root){
//        if(root == null){
//            return 0;
//        }
//        int left = getDepth(root.left);
//        int right = getDepth(root.right);
//        return (left>right?left:right)+1;
//    }
//}
////6.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。（假设输入的前序遍历和中序遍历的结果中都不含重复的数字
///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode(int x) { val = x; }
// * }
// */
//class Solution {
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
//    }
//
//    private TreeNode buildTree(int[] preorder, int ps, int pe, int[] inorder, int is, int ie) {
//        if (ps > pe) {
//            return null;
//        }
//        // 前序遍历第一个节点为根节点
//        int rootVal = preorder[ps];
//        TreeNode root = new TreeNode(rootVal);
//        // 确定根节点在中序遍历中的位置
//        int im = is;
//        while (im < ie && inorder[im] != rootVal) {
//            im++;
//        }
//        // 根据根节点在中序遍历中的位置得到左右子树的前序遍历和中序遍历序列
//        root.left = buildTree(preorder, ps + 1, ps + im - is, inorder, is, im - 1);
//        root.right = buildTree(preorder, ps + im - is + 1, pe, inorder, im + 1, ie);
//        return root;
//    }
//}
////7.在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
//public class Solution {
//    public boolean Find(int [][] array,int target) {
//        int row=0;
//        int col=array[0].length-1;
//        while(row<=array.length-1&&col>=0){
//            if(target==array[row][col])
//                return true;
//            else if(target>array[row][col])
//                row++;
//            else
//                col--;
//        }
//        return false;
//
//    }
//}
//
////8.给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
//class Solution {
//    public int lengthOfLongestSubstring(String s) {
//        int maxLength = 0;
//        char[] chars = s.toCharArray();
//        int leftIndex = 0;
//        for (int j = 0; j < chars.length; j++) {
//            for (int innerIndex = leftIndex; innerIndex < j; innerIndex++) {
//                if (chars[innerIndex] == chars[j]) {
//                    maxLength = Math.max(maxLength, j - leftIndex);
//                    leftIndex = innerIndex + 1;
//                    break;
//                }
//            }
//        }
//        return Math.max(chars.length - leftIndex, maxLength);
//    }
//}
////9.输入一个字符串,按字典序打印出该字符串中字符的所有排列
//import java.util.ArrayList;
//        import java.util.TreeSet;
//public class test {
//    public ArrayList<String> Permutation(String str) {
//        ArrayList<String> result = new ArrayList<String>();//根据返回类型需要
//        if(str==null||str.length()==0){
//            return result;
//        }
//        char[] chars = str.toCharArray();
//        TreeSet<String> res = new TreeSet<String>(); //用于排序输出
//        getResult(chars,0,str.length()-1,res);
//        result.addAll(res) ;//添加到ArrayList
//        return result ;
//    }
//    public void getResult(char[] chars,int start,int end,TreeSet<String> res){
//        if(start==end)res.add(String.valueOf(chars));
//        else{
//            for(int i=start;i<=end;i++){
//                swap(chars,start,i);
//                getResult(chars,start+1,end,res);
//                swap(chars,start,i);//在换回来
//            }
//        }
//    }
//    public void swap(char[] chars,int a,int b){
//        if(a==b)return;
//        else{
//            char temp = chars[a];
//            chars[a] = chars[b];
//            chars[b] = temp;
//        }
//    }
//}
//    //10.	实现快速排序算法
//    public static void quickSort(int[] arr, int low, int high) {
//
//        int start = low;
//        int end = high;
//
//        int key = arr[low];
//        while (start < end){
//            //第一次从后往前查
//            while (end > start && arr[end] >= key){
//                end --;
//            }
//            if (arr[end]<=key){
//                int temp = arr[end];
//                arr[end] = arr[start];
//                arr[start] = temp;
//            }
//
//            //第二次从前往查
//            while (end > start && arr[start] <= key){
//                start ++;
//            }
//            if (arr[start] >= key){
//                int temp = arr[start];
//                arr[start] = arr[end];
//                arr[end] = temp;
//            }
//            //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的 值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
//        }
//
//        //递归
//        if (start > low){
//            //左边序列。第一个索引位置到关键值索引-1
//            quickSort(arr,low,start-1);
//
//        }
//
//        if (end < high){
//            quickSort(arr, end + 1, high);
//        }
//
//    }
//
//
//
//
//
//
